\section{Discussion of Parallelization Techniques}
\label{sec:disc}

In implementing our approach, we encountered several unanticipated difficulties, which we present here as drawbacks of using CUDA.  In evaluating our implementation, we uncovered a few flaws, which we present here as potential problems with our implementation.

\subsection{Weaknesses of CUDA and GPUs}

In our experience, we uncovered a few drawbacks in using CUDA and GPUs.  The first of these is that it is not possible to call \texttt{printf} from the GPU, so we could not use print statements to debug our GPU functions.  The second is that in the previous particle simulation assignment, we relied on recursion to implement a $O(n)$ serial particle simulation.  However, we were not able to use recursion on the GPU, so we had to start from scratch with a different $O(n)$ serial implementation.  A third drawback, which we mentioned, is that we were unable to take advantage of the \texttt{C++ STL}; this necessitated the use of, for instance, the bin sizes structure.

\subsection{Potential Problems with Our Implementation}

We note three potential problems with our implementation.  The first, which we mentioned previously, is that the binning procedure takes longer than the actual calculation for small simulation sizes.  Thus, the improvement over the naive implementation does not approach ideal until simulation sizes of approximately 10000 particles or more.

A second problem is that in our \texttt{fill\_bins} procedure, there can be potential race conditions when more than one thread attempts to update the same bin.  In practice, however, we did not observe these because the binning occurs on such a fine scale that there is never more than one particle per bin, and most bins are empty.

A third problem is that due to implementation difficulties, we found it easiest to assume that bins would never contain more than four particles.  This was true in practice and caused no problems.  However, it is not always a valid assumption.  This problem would have been avoidable if we had been able to use the \texttt{C++ STL vector} class, which resizes automatically.
